package cn.good.yan.sf.t6.priority;

import cn.good.yan.sf.t6.Queue;

/**
 * 6 优先级队列 - 基于 堆（小顶堆）
 * 从数组0节点开始
 * 获取父节点： (i + 1) / 2
 * 获取子节点： 2i + 1
 * 从数组1节点开始
 * 获取父节点： (i) / 2
 * 获取子节点： 2i
 *
 * @author shengren.yan
 * @create 2024-07-22
 */
@SuppressWarnings("all")
public class PriorityQueue4<E extends Priority> implements Queue<E> {

    Priority[] arr;
    int size = 0;

    public PriorityQueue4(int num) {
        arr = new Priority[num];
    }

    @Override
    public boolean offer(E e) {
        if (isFull()) {
            return false;
        }
        int son = size++;
        int fater = (son - 1) / 2;
        while (son > 0 && e.priority() < arr[fater].priority()) {
            arr[son] = arr[fater];
            son = fater;
            fater = (son - 1) / 2;
        }
        arr[son] = e;
        return true;
    }

    @Override
    public E pool() {
        if (isEmpty()) {
            return null;
        }
        jh(0, size - 1);
        E e = (E) arr[size - 1];
        arr[size - 1] = null;
        size--;
        // 下潜
        down(0);
        return e;
    }

    // 交换位置
    private void jh(int i, int j) {
        E t = (E) arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // 下潜
    private void down(int i) {
        int max = i;
        int left = 2 * i + 1;
        int right = left + 1;
        if (left < size && arr[left].priority() < arr[max].priority()) {
            max = left;
        }
        if (right < size && arr[right].priority() < arr[max].priority()) {
            max = right;
        }
        if (max != i) {
            jh(i, max);
            down(max);
        }
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        E e = (E) arr[0];
        return e;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == arr.length;
    }


    public static void main(String[] args) {
        PriorityQueue4<Entry> queue = new PriorityQueue4<>(6);
        // 添加元素
        System.out.println("添加元素：" + queue.offer(new Entry("q1", 4)));
        System.out.println("添加元素：" + queue.offer(new Entry("q2", 3)));
        System.out.println("添加元素：" + queue.offer(new Entry("q3", 2)));
        System.out.println("添加元素：" + queue.offer(new Entry("q4", 5)));
        System.out.println("添加元素：" + queue.offer(new Entry("q5", 1)));
        System.out.println("添加元素：" + queue.offer(new Entry("q7", 9)));
        System.out.println("添加元素：" + queue.offer(new Entry("q8", 10)));
        System.out.println("---------------------------");
        System.out.println("获取头元素：" + queue.peek());
        System.out.println("获取头元素：" + queue.peek());
        System.out.println("---------------------------");
        System.out.println("移除头元素：" + queue.pool());
        System.out.println("移除头元素：" + queue.pool());
        System.out.println("移除头元素：" + queue.pool());
        System.out.println("移除头元素：" + queue.pool());
        System.out.println("移除头元素：" + queue.pool());
        System.out.println("移除头元素：" + queue.pool());
        System.out.println("移除头元素：" + queue.pool());
        // 正序打印

    }

}
